//
// Created by win10 on 24-12-18.
//
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    //1.数据域
    int data;
    //左右孩子指针
    struct Ltree *lchild;
    struct Ltree *rchild;
}Ltree;

//2.创建新节点
Ltree *createLtree(int value) {
    //为子节点分配空间
    Ltree *newNode = (Ltree *) malloc(sizeof(Ltree));
    //鲁棒性判断
    if(!newNode) {
        printf("内存分配失败\n");
        return NULL;
    }
    //值的分配
    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    return newNode;
}

//查找某个值
Ltree *search(Ltree *root, int key) { //1.root 树的根节点 2.key需要查找的值
    if(!root) {
        return NULL;
    }
    if(root->data == key) {
        return root;
    }
    if(key<root->data) {
        return search(root->lchild, key);
    }
    if(key>root->data) {
        return search(root->rchild, key);
    }
}

//插入某个数值
Ltree *insert(Ltree *root, int key) {
    if(!root) {
        root=createLtree(key);
    }
    else if(key<root->data) {
        root->lchild=insert(root->lchild, key);
    }else if(key>root->data) {
        root->rchild=insert(root->rchild, key);
    }else {
        printf("node has been existed");
        return root;
    }
    return root;
}

// 中序遍历（查看二叉排序树内容）
void inorderTraversal(Ltree* root) {
    if (root != NULL) {
        inorderTraversal(root->lchild);
        printf("%d ", root->data);
        inorderTraversal(root->rchild);
    }
}

int main()
{
    Ltree* NodeA = createLtree(122);
    Ltree* NodeB = createLtree(99);
    Ltree* NodeC = createLtree(110);
    Ltree* NodeD = createLtree(105);
    Ltree* NodeE = createLtree(250);

    NodeA->lchild = NodeB;
    NodeA->rchild = NodeE;

    NodeB->rchild = NodeC;
    NodeC->lchild = NodeD;

    inorderTraversal(NodeA);


    Ltree * result = search(NodeA, 105);
    printf("\n%d\n", result->data);

    NodeA = insert(NodeA, 103);
    inorderTraversal(NodeA);
}

